package offerbook;

import utils.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


/**
 * Created at 2019/11/1 0001 上午 8:51
 * 方式1：递归统计所有可能的路径，返回路径中最长的。时间O(n),空间最大是O(logn)
*          对一颗满二叉，路径树就是其叶子节点个数，也就是最后一层个数，
 * 方式2：递归遍历统计，O(n)时间复杂度
 */
public class Code39_TreeDepth {
    /**
     * 方式1：通过
     */
    public static int getDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        List<Integer> totalPath = new ArrayList<>();
        List<TreeNode> path = new ArrayList<>();
        preOrder(root,totalPath,path);
        return Collections.max(totalPath);
    }
    private static void preOrder(TreeNode root,List<Integer> totalPath,List<TreeNode> path){
        if(root == null){
            return;
        }
        //添加到当前路径
        path.add(root);
        //处理叶子节点
        if(root.left == null && root.right == null){
            totalPath.add(path.size());
        }
        preOrder(root.left,totalPath,path);
        preOrder(root.right,totalPath,path);
        //出栈最后一个元素，返回上一级递归
        path.remove(path.size() - 1);
    }

    /**
     * 方式2：递归遍历
     */
    public static int getDepth1(TreeNode root){
        if(root == null){
            return 0;
        }
        return getLevel(root);
    }

    private static int getLevel(TreeNode root) {
        //叶子节点所在的层级
        if(root == null){
            return 0;
        }
        //当前树的高度是 左右孩子最大的高度 + 1
        return Math.max(getLevel(root.left),getLevel(root.right))+1;
    }


}
